/*
 * @lc app=leetcode.cn id=309 lang=cpp
 *
 * [309] 最佳买卖股票时机含冷冻期
 */

// @lc code=start
class Solution
{
public:
  int maxProfit(vector<int>& prices)
  {
    int n = prices.size();
    // dp[i][0] 手上没股票
    // dp[i][1] 手上有股票
    vector<vector<int>> dp(n + 1, vector<int>(2));
    dp[1][1] = -prices[0];
    for (int i = 2; i <= n; ++i) {
      // 今天没股票，可能前几天没股票，也可能是前几天有股票但今天卖出
      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
      // 今天有股票，可能是前几天有股票，也可能是前天卖出，但今天买上
      dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]);
    }
    return dp[n][0];
  }
};
// @lc code=end
